home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / etc / trie-gen / compact.cc < prev    next >
C/C++ Source or Header  |  1994-02-06  |  13KB  |  402 lines
  1. /* Compact a sparse 2-D matrix.  Uses the Tarjan and Yao algorithm
  2.    taken from the article ``Storing a Sparse Table'' in CACM, 1979.
  3.  
  4.    Copyright (C) 1989 Free Software Foundation, Inc.
  5.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  6.    
  7.    This file is part of GNU TRIE-GEN.
  8.    
  9.    GNU TRIE-GEN is free software; you can redistribute it and/or modify
  10.    it under the terms of the GNU General Public License as published by
  11.    the Free Software Foundation; either version 1, or (at your option)
  12.    any later version.
  13.    
  14.    GNU TRIE-GEN is distributed in the hope that it will be useful,
  15.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17.    GNU General Public License for more details.
  18.    
  19.    You should have received a copy of the GNU General Public License
  20.    along with GNU trie-gen; see the file COPYING.  If not, write to
  21.    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  22.  
  23. #include <stdio.h>
  24. #include <builtin.h>
  25. #include <limits.h>
  26. #include <new.h>
  27. #include <std.h>
  28. #include <assert.h>
  29. #include "renew.h"
  30. #include "compact.h"
  31.  
  32. /* Essentially provides the functionality of `calloc.' */
  33.  
  34. static inline void *
  35. operator new (size_t elem_size, int size)
  36. {
  37.   void *temp = new char[elem_size * size];
  38.   memset (temp, 0, elem_size * size);
  39.   return temp;
  40. }
  41.  
  42. /* Essentially combines the functionality of `realloc' and `calloc'. */
  43.  
  44. static inline void *
  45. operator new (size_t elem_size, void *old_ptr, int old_size, int new_size)
  46. { 
  47.   old_ptr = new (old_ptr, new_size * elem_size) char;
  48.   memset ((char*)old_ptr + old_size * elem_size, 0,
  49.       (new_size - old_size) * elem_size);
  50.   return old_ptr;
  51. }
  52.  
  53. /* Initializes the internal form in the case that the user passes
  54.    in a pointer to an already existing 2-dimensional matrix.  Note
  55.    that by declaring the matrix to be a 1-dimensional array we
  56.    can perform the col and row offset calculations ourselves and
  57.    handle matrices with fixed, but arbitrary-sized columns and rows. */
  58.  
  59. Compact_Matrix::Compact_Matrix (ITEM_TYPE *mat, int rows, int cols):
  60.      matrix (mat), max_rows (rows), total_cols (cols), current_rows (rows)
  61. {
  62.   init (rows);
  63.  
  64.   for (int i = 0; i < max_rows; i++)
  65.     for (int j = 0; j < total_cols; j++)
  66.       if (matrix[i * total_cols + j] != 0)
  67.         {
  68.           ITEM_TYPE value = matrix[i * total_cols + j];
  69.           total_entries++;
  70.           row_vec[i].count++;
  71.           row_vec[i].col_list = new Column_Node (row_vec[i].col_list, j, value);
  72.         }
  73. }
  74.  
  75. /* Initializer for the case where we don't have a previously created
  76.    matrix to play with.  DEFAULT_ROWS represents the best first
  77.    approximation as to the number of rows in the matrix.  However, this
  78.    buffer is resized as needed, so the algorithm isn't overly penalized
  79.    for a bad first guess. */
  80.  
  81. Compact_Matrix::Compact_Matrix (int default_rows): max_rows (default_rows)
  82. {
  83.   current_rows = 0;
  84.   total_cols = 0;
  85.   matrix = 0;
  86.  
  87.   init (default_rows);
  88. }
  89.  
  90. void Compact_Matrix::init(int rows)
  91. {
  92.   max_col_count = 0;
  93.   total_entries = 0;
  94.   compressed_len = -1;
  95.   row_offsets = 0;
  96.   checks = 0;
  97.   bucket_vec = 0;
  98.   values = 0;
  99.  
  100.   row_vec = rows ? new Row_Node[rows] : 0;
  101. }
  102.  
  103. /* Returns the `matrix[i][j]' item in the sparse 2-dimensional matrix.
  104.    Note that if the matrix is very sparse the number of items in each
  105.    COL_LIST will be very short, hence linear search is not too inefficent. */
  106.  
  107. ITEM_TYPE 
  108. Compact_Matrix::operator () (int i, int j)
  109. {
  110.   assert (i >= 0 && i < current_rows && j >= 0);
  111.   
  112.   for (Column_Node *col_list = row_vec[i].col_list; col_list; col_list = col_list->next)
  113.     if (col_list->index == j)
  114.       return col_list->value;
  115.  
  116.   return 0;
  117. }
  118.  
  119. /* Sets `matrix[i][j]' to VALUE.  ROW_VEC is dynamically resized, if
  120.    necessary.  At the moment the new entry is simply pushed onto the
  121.    linked list of COL_LIST entries.  If there aren't many elements then
  122.    this will not be too inefficient for later retrieval. */
  123.  
  124. void
  125. Compact_Matrix::operator () (int i, int j, ITEM_TYPE value)
  126. {
  127.   if (i >= max_rows)
  128.     resize (((max_rows * 2) > (i + 1)) ? (max_rows * 2) : (i + 1));
  129.   row_vec[i].col_list = new Column_Node (row_vec[i].col_list, j, value);
  130.   total_entries++;
  131.   row_vec[i].count++;
  132.   if (current_rows < (i + 1))
  133.     current_rows = i + 1;
  134. }
  135.  
  136. /* Enlarges the ROW_VEC from CURR_ROWS to NEW_SIZE. */
  137.  
  138. void 
  139. Compact_Matrix::resize (int new_size)
  140. {
  141.   Row_Node *temp = new Row_Node[max_rows = new_size];
  142.   
  143.   memcpy ((void *) temp, (void *) row_vec, current_rows * sizeof *row_vec);
  144.   delete row_vec;
  145.   row_vec = temp;
  146. }
  147.  
  148. /* Calls the functions that compact the table and generate the resulting
  149.    lookup scheme. */
  150.  
  151. void
  152. Compact_Matrix::output (void)
  153. {
  154.   bucket_sort ();
  155.   first_fit_decreasing ();
  156.   output_arrays ();
  157.   output_lookup ();
  158. }
  159.  
  160. /* Performs a bucket sort so that all rows with the same number of non-null
  161.    entries are treated as part of the same equivalence class.  This
  162.    operation is very fast! */
  163.  
  164. void 
  165. Compact_Matrix::bucket_sort (void)
  166. {
  167.   for (int i = 0; i < current_rows; i++)
  168.     {
  169.       if (max_col_count < row_vec[i].count)
  170.         max_col_count = row_vec[i].count;
  171.     }
  172.   
  173.   bucket_vec = new (max_col_count + 1) Column_Node *;
  174.  
  175.   for (i = 0; i < current_rows; i++)
  176.     bucket_vec[row_vec[i].count] = new Column_Node (bucket_vec[row_vec[i].count], i, 0);
  177. }
  178.  
  179. /* Useful macros to clarify subsequent code.  They should probably be made
  180.    into member functions... */
  181. #define STARTING_ROW_OFFSET(X) (row_offsets[(X)])
  182. #define LARGEST_COL_VALUE(X) (row_vec[(X)].col_list->index)
  183. #define COL_LIST(X) (row_vec[(X)].col_list)
  184. #define COL_COUNT(X) (row_vec[(X)].count)
  185. #define COL_INDEX(X) ((X)->index)
  186. #define ROW_INDEX(X) ((X)->index)
  187.  
  188. const int     MAX_ASCII_RANGE    = 128;
  189.  
  190. /* Performs sparse 2-dimensional array compaction suitable for use with the
  191.    `double-offset indexing' (used by Bison and FLEX to compact the size of
  192.    the sparse LR parsing tables and DFA's).  This function implements the
  193.    `first fit decreasing' heuristic described in Tarjan and Yao's paper 
  194.    ``Storing a Sparse Table'' in CACM, 1979. */
  195.  
  196. void 
  197. Compact_Matrix::first_fit_decreasing (void)
  198. {
  199.   /* Bit-vector and counter that records if a row/col location is already set. */
  200.   int    current_max = current_rows
  201.     + ((total_cols > MAX_ASCII_RANGE) ? total_cols : MAX_ASCII_RANGE);
  202.   char *already_assigned = (char *) malloc (current_max);
  203.   
  204.   memset (already_assigned, 0, current_max);
  205.   row_offsets = new (current_rows) int;
  206.   values      = new (current_max) ITEM_TYPE;
  207.   checks      = new (current_max) int;
  208.  
  209.   for (int row_index = max_col_count; row_index >= 0; row_index--)
  210.     if (bucket_vec[row_index])
  211.  
  212.       /* Process every row in the `equivalence class' of rows containing the
  213.          same number of non-null column entries. */
  214.  
  215.       for (Column_Node *rows_list = bucket_vec[row_index]; rows_list; rows_list = rows_list->next)
  216.         {
  217.           int row        = ROW_INDEX (rows_list);
  218.           int row_offset = STARTING_ROW_OFFSET (row);
  219.           
  220.           /* Process every column index in the current row. */
  221.  
  222.           for (Column_Node *col_list = COL_LIST (row); ;)
  223.             {
  224.               int col = COL_INDEX (col_list);
  225.  
  226.               /* If we exceed the boundaries it's time to resize various buffers. */
  227.               if (row_offset + col >= current_max)
  228.                 {
  229.                   int   new_size = ((current_max > (row_offset + col)) ? current_max : (row_offset + col)) * 2;
  230.                   already_assigned =
  231.               (char *) realloc (already_assigned, new_size);
  232.  
  233.           memset (already_assigned + current_max, 0,
  234.               new_size - current_max);
  235.                   values = new (values, current_max, new_size) int;
  236.                   checks = new (checks, current_max, new_size) int;
  237.                   current_max *= 2;
  238.                 }
  239.               if (already_assigned[row_offset + col])
  240.                 {
  241.                   /* Efficiency hack to skip over obvious collisions. */
  242.  
  243.                   while (++row_offset + col < current_max && already_assigned[row_offset + col]) 
  244.                     ;
  245.  
  246.                   /* Reset col_list and begin again (with new row offset). */
  247.                   col_list = COL_LIST (row);
  248.                 }
  249.               else if ((col_list = col_list->next) == 0)
  250.                 break;
  251.             }
  252.  
  253.           /* No more collisions exist.  Record the positions for the next round. */
  254.  
  255.           for (col_list = COL_LIST (row); col_list; col_list = col_list->next)
  256.             {
  257.               int offset = row_offset + COL_INDEX (col_list);
  258.  
  259.               already_assigned[offset] = 1;
  260.               if (compressed_len < offset)
  261.         compressed_len = offset;
  262.               values[offset] = col_list->value;
  263.               checks[offset] = row;
  264.             }
  265.  
  266.           /* Need to reset this once all is said and done! */
  267.           STARTING_ROW_OFFSET (row) = row_offset;
  268.         }
  269.   free(already_assigned);
  270. }
  271.  
  272. /* Generates the three arrays that comprise the `double-offset index'
  273.    scheme.  This is a bit messy, since I'm trying to neatly format
  274.    the generated tables and also determine the smallest (in bytes)
  275.    type declarations necessary to represent the elements of the tables. */
  276.  
  277. void 
  278. Compact_Matrix::output_arrays ()
  279. {
  280.   const int COL_WIDTH = 12;
  281.         int max_number = 0;
  282.         int count;
  283.       
  284.   printf ("#if !defined(__STDC__) && !defined(__cplusplus)\n");
  285.   printf ("#define const\n");
  286.   printf ("#define signed\n");
  287.   printf ("#endif\n\n");
  288.   printf ("#define YY_LAST %d\n", compressed_len);
  289.       
  290.   for (int i = 0; i < current_rows; i++)
  291.     {
  292.       if (max_number < row_offsets[i])
  293.         max_number = row_offsets[i];
  294.     }
  295.  
  296.   count = max_number;
  297.   for (int field_width = 1; (count /= 10) > 0; field_width++)
  298.     ;
  299.  
  300.   printf ("\nstatic const unsigned %s yy_rows[%d] = \n{\n  ",
  301.           max_number < UCHAR_MAX ? "char" : max_number < USHRT_MAX ? "short" : "int",
  302.           current_rows);
  303.       
  304.   for (i = 0; i < current_rows; i++)
  305.     printf ("%*d,%s", field_width, row_offsets[i], (i + 1) % COL_WIDTH ? " " : "\n  ");
  306.       
  307.   max_number = 0;
  308.  
  309.   for (i = 0; i < compressed_len + 1; i++)
  310.     {
  311.       if (max_number < checks[i])
  312.         max_number = checks[i];
  313.     }
  314.  
  315.   count = max_number;
  316.   for (field_width = 1; (count /= 10) > 0; field_width++)
  317.     ;
  318.  
  319.   printf ("\n};\n\nstatic const unsigned %s yy_check[%d] = \n{\n  ",
  320.           max_number < UCHAR_MAX ? "char" : max_number < USHRT_MAX ? "short" : "int",
  321.           compressed_len + 1);
  322.       
  323.   for (i = 0; i < compressed_len + 1; i++)
  324.     printf ("%*d,%s", field_width, checks[i], (i + 1) % COL_WIDTH ? " " : "\n  ");
  325.       
  326.   max_number = 0;
  327.  
  328.   for (i = 0; i < compressed_len + 1; i++)
  329. #ifdef __GNUC__
  330.     max_number >?= abs (values[i]);
  331. #else
  332.     {
  333.       int tmp = abs (values[i]);
  334.       if (max_number < tmp)
  335.         max_number = tmp;
  336.     }
  337. #endif
  338.  
  339.   count = max_number;
  340.   for (field_width = 2; (count /= 10) > 0; field_width++)
  341.     ;
  342.  
  343.   printf ("\n};\n\nstatic const %s yy_next[%d] = \n{\n  ",
  344.           max_number < SCHAR_MAX ? (CHAR_MIN == 0 ? "signed char" : "char")
  345.       : max_number < SHRT_MAX ? "short" : "int",
  346.           compressed_len + 1);
  347.       
  348.   for (i = 0; i <= compressed_len; i++)
  349.     printf ("%*d,%s", field_width, values[i], (i + 1) % COL_WIDTH ? " " : "\n  ");
  350.       
  351.   printf ("\n};\n\n");
  352. }
  353.  
  354. /* Generates the `double-offset index' function, that provides the
  355.    value stored in the location referenced by parameters ROW and COL. */
  356.  
  357. void 
  358. Compact_Matrix::output_lookup (void)
  359. {
  360.   printf ("static inline int\nnext_state "
  361.           "(int row, int col)\n{\n  int state_index = yy_rows[row] + col;\n\n"
  362.           "  if (state_index > YY_LAST || yy_check[state_index] != row)\n    "
  363.           "return 0;\n  else\n    return yy_next[state_index];\n}\n");
  364. }
  365.  
  366. /* Useful debugging routine. */
  367.  
  368. void
  369. Compact_Matrix::dump_entries (void)
  370. {
  371.   for (int i = 0; i < current_rows; i++)
  372.     if (row_vec[i].col_list)
  373.       {
  374.         Column_Node *temp = row_vec[i].col_list;
  375.       
  376.         fprintf (stderr, "row %d's count = %d, cols = ", i, row_vec[i].count);
  377.  
  378.         do { fprintf (stderr, "%d ", temp->index); } while (temp = temp->next);
  379.  
  380.         putc ('\n', stderr);
  381.       }
  382. }
  383.  
  384. /* Useful debugging routine. */
  385.  
  386. void 
  387. Compact_Matrix::dump_bucket (void)
  388. {
  389.   for (int i = 0; i < total_entries; i++)
  390.     if (bucket_vec[i])
  391.       {
  392.         Column_Node *temp = bucket_vec[i];
  393.         
  394.         fprintf (stderr, "bucket %d = ", i);
  395.  
  396.         do { fprintf (stderr, "%d ", temp->index); } while (temp = temp->next);
  397.  
  398.         putc ('\n', stderr);
  399.       }
  400. }
  401.  
  402.